#coding=utf-8 
'''
Created on 2012-8-28
@author: gazhang
'''
#http://blog.csdn.net/v_JULY_v/article/details/6057286
#problem 24 链表操作，单链表就地逆置
#problem 42 请修改append函数，利用这个函数实现（链表）：两个非降序链表的并集，1->2->3 和 2->3->5 并为 1->2->3->5 另外只能输出结果，不能修改两个链表的数据。
class LinkedNode():
    '''
    classdocs
    '''
    def __init__(self,_next,_val):
        self.next=_next
        self.value=_val

def reverseUsingRecrusive(nod):
    if nod is not None and nod.next is not None:
        head=reverseUsingRecrusive(nod.next)
        nod.next.next=nod
        nod.next=None
        return head
    else:
        return nod
        
def reverse(nod):
    _p1=None
    _p2=nod
    while(_p2 is not None):
        _p3=_p2.next
        _p2.next=_p1
        _p1=_p2
        _p2=_p3
    return _p1

def _print(nod):
    _p1=nod
    while(_p1 is not None):
        print _p1.value
        _p1=_p1.next
        
def mergeSorted(nod1, nod2):
    head = LinkedNode(-1, None)
    p = head
    while(nod1 is not None and nod2 is not None):
        if(nod1.value < nod2.value):
            p.next = nod1
            p = nod1
            nod1 = nod1.next
        elif(nod1.value==nod2.value):
            nod1=nod1.next
        else:
            p.next = nod2
            p = nod2
            nod2 = nod2.next
    if(nod1 is not None):
        p.next=nod1
    elif(nod2 is not None):
        p.next=nod2
    return head.next 
    
#Test Reverse
nod1=LinkedNode(None,1)
nod2=LinkedNode(nod1,2)
nod3=LinkedNode(nod2,3)
nod4=LinkedNode(nod3,4)
nod5=LinkedNode(nod4,5) 
new_head=reverse(nod5) 
_print(new_head)      
        
        